#include "hash.h"
#include <string.h>

#define TAMANIOINICIAL 32
#define VACIO	0
#define OCUPADO	1
#define LAPIDA	2

/* ******************************************************************
 *                    INVARIANTES DEL TDA HASH
 * *****************************************************************/

/* Los elementos que agrega el usuario al hash estaran en la posicion correspondiente
otorgada por la funcion de hashing o n lugares despues de esta, pero en la misma isla, es decir,
no puede haber espacios vacios entre la posicion otorgada y en la que realmente se encuentra el elemento.

Además, no existiran 2 elementos distintos con la misma clave dentro del hash.

Al implementar un hash cerrado, entendemos por despues la posicion siguiente en el vector de elementos si la actual
no es la final, y la primer posicion en el caso contrario. Al ser este un recorrido circular, nos aseguraremos de
redimensionar el hash convenientemente para evitar loops infinitos al buscar o agregar elementos.

El atributo cantidad se correspondera con la cantidad de elementos actuales en el hash, sin contar borrados o vacios.
El atributo tamanio se correspondera con la cantidad actual de posiciones ocupadas o no del hash.
El atributo ocupados se correspondera con la cantidad de elementos actuales en el hash, sin contar vacios.

 *******************************************************************/

struct hash_iter{
	const hash_t* hash;
	size_t index;	
};

struct hash_elemento{
	char* clave;
	void* valor;
	int estado;
};

struct hash{
	hash_elemento_t** vector;
	size_t tam;
	size_t cantidad;
	size_t ocup;
	hash_destruir_dato_t destruir_dato;
};

void index_avanzar(const hash_t* hash, int* prev_index)
{
	(*prev_index)++;
	if (hash->tam == *prev_index) *prev_index = 0;
}

size_t hash_index(const hash_t* hash, const char *clave)
{
    unsigned hashval;
    
    for (hashval = 0; *clave != '\0'; clave++)
        hashval = *clave + 31 * hashval;
    return hashval%(hash->tam);
}

void vector_destruir(hash_elemento_t** vector, size_t tamanio, hash_destruir_dato_t destruir_dato)
{
	for (int i = 0; i < tamanio; i++)
	{
		if (vector[i]->estado == OCUPADO){
			if (destruir_dato) destruir_dato(vector[i]->valor);
		}
		if (vector[i]->estado != VACIO){
			free(vector[i]->clave);
		}		
		free(vector[i]);
	}
	free(vector);
}

hash_elemento_t** vector_crear(size_t tamanio)
{
	hash_elemento_t** vector = malloc(sizeof(void*)*tamanio);
	if (!vector) return NULL;
	
	for (int i = 0; i < tamanio; i++)
	{
		hash_elemento_t* nuevo_elemento = malloc(sizeof(hash_elemento_t));
		if (!nuevo_elemento)
		{	// Elimina todos los elementos creados
			for (int j = (i - 1); j >= 0; j--)
			{
				free(vector[j]);
			}
			free(vector);
			return NULL;
		}
		vector[i] = nuevo_elemento;
		vector[i]->estado = VACIO;
	}
	return vector;
}

void hash_vector_guardar(hash_t *hash, const char *clave, void *dato)
{
	int index = hash_index(hash, clave);
	while (hash->vector[index]->estado != VACIO)
	{
		if (strcmp(hash->vector[index]->clave, clave) == 0)
		{
			if (hash->destruir_dato) hash->destruir_dato(hash->vector[index]->valor);
			break;
		}
		index_avanzar(hash, &index);
	}
	if (hash->vector[index]->estado == VACIO)
		hash->vector[index]->clave = malloc(sizeof(char)*strlen(clave)+sizeof(char));
		strcpy(hash->vector[index]->clave, clave);
		hash->ocup++;
	if (hash->vector[index]->estado != OCUPADO){
		hash->cantidad++;
		hash->vector[index]->estado = OCUPADO;
	}
	hash->vector[index]->valor = dato;
}

bool hash_redimensionar(hash_t *hash)
{
	float relacion = (float)(hash->ocup)/(hash->tam);
	// Solo se redimensionara el hash si hay más de 3/4 ocupados
	if (relacion < (float)3/4 || hash->ocup < 16) return false;
	
	// Creo un nuevo hash que va a reemplazar al viejo
	hash_t* hash_nuevo = hash_crear(hash->destruir_dato);
	if (!hash_nuevo) return false;
	
	if (relacion >= (float)3/4)
	{	// Asigno el nuevo tamanio del hash
		hash_nuevo->tam = hash->tam*4;
	}

	// Destruyo el vector que se crea con el nuevo hash.
	vector_destruir(hash_nuevo->vector, TAMANIOINICIAL, NULL);
	// Y creo un vector del tamanio antes elegido.
	hash_nuevo->vector = vector_crear(hash_nuevo->tam);
	if (!hash_nuevo->vector) return false;

	hash_iter_t *iter = hash_iter_crear(hash);
	if (!iter) return false;
	
	const char *elemento;
	while(!hash_iter_al_final(iter))
	{	// Copio elemento a elemento del hash viejo al nuevo.
		elemento = hash_iter_ver_actual(iter);
		hash_vector_guardar(hash_nuevo, elemento, hash_obtener(hash, elemento));
		hash_iter_avanzar(iter);
	}
	hash_iter_destruir(iter);
	
	// Creo un tercer hash donde voy a guardar el vector original para no perder la referencia
	// y luego poder liberarlo.
	// Paso null para destruir_dato ya que si los datos que nos envian en el hash original estan
	// en el heap estos van a ser eliminados dos veces luego de copiarlos al hash nuevo.
	// Se eliminarian una vez en el original y la otra en la copia, dando un multiple free.
	hash_t* hash_temp = hash_crear(NULL);
	if (!hash_temp) return false;
	// Destruyo el vector que se crea con el nuevo hash.
	vector_destruir(hash_temp->vector, TAMANIOINICIAL, NULL);
	
	hash_temp->vector = hash->vector;
	hash_temp->tam = hash->tam;
	
	hash->vector = hash_nuevo->vector;
	hash->tam = hash_nuevo->tam;
	hash->cantidad = hash_nuevo->cantidad;
	hash->ocup = hash_nuevo->ocup;
	hash_destruir(hash_temp);
	// Solamente hago free al struct del hash nuevo ya que este aun contiene las referencias al vector
	// nuevo, si hago hash_destruir estas tambien se destruirian.
	free(hash_nuevo);
	return true;
}

hash_t *hash_crear(hash_destruir_dato_t destruir_dato)
{
	hash_t* hash_nuevo = malloc(sizeof(hash_t));
	if (!hash_nuevo) return NULL;
	
	hash_nuevo->cantidad = 0;
	hash_nuevo->tam = TAMANIOINICIAL;
	hash_nuevo->ocup = 0;
	hash_nuevo->destruir_dato = destruir_dato;
	
	hash_nuevo->vector = vector_crear(TAMANIOINICIAL);
	if (!hash_nuevo->vector)
	{
		free(hash_nuevo);
		return NULL;
	}
	
	return hash_nuevo;
}

bool hash_guardar(hash_t *hash, const char *clave, void *dato)
{
	if (!hash) return false;
	
	hash_redimensionar(hash);
	
	hash_vector_guardar(hash, clave, dato);
	return true;
}

int hash_obtener_index(const hash_t *hash, const char *clave)
{
	if (!hash) return -1;
	
	int index = hash_index(hash, clave);
	while (1)
	{
		if (hash->vector[index]->estado != VACIO){			
			if (strcmp(hash->vector[index]->clave, clave) == 0) break;
		}
		else return -1; // Termino la isla y no fue encontrado
		index_avanzar(hash, &index);
	}
	if (hash->vector[index]->estado == LAPIDA) return -1;
	return index;
}

void *hash_borrar(hash_t *hash, const char *clave)
{
	if (!hash) return NULL;
	
	int index = hash_obtener_index(hash, clave);
	if (index == -1)return NULL;
	hash->vector[index]->estado = LAPIDA;
	hash->cantidad--;
	return hash->vector[index]->valor;
}

void *hash_obtener(const hash_t *hash, const char *clave)
{
	if (!hash) return NULL;
	
	int index = hash_obtener_index(hash, clave);
	if (index == -1)return NULL;
	return hash->vector[index]->valor;
}

bool hash_pertenece(const hash_t *hash, const char *clave)
{
	if (!hash) return NULL;

	int index = hash_obtener_index(hash, clave);
	if (index == -1)return false;
	
	return true;
}

int hash_cantidad(const hash_t *hash)
{
	if (!hash) return -1;
	return hash->cantidad;
}

void hash_destruir(hash_t *hash)
{
	vector_destruir(hash->vector, hash->tam, hash->destruir_dato);
	free(hash);
}

hash_iter_t *hash_iter_crear(const hash_t *hash)
{
	if (!hash) return NULL;

	hash_iter_t* nuevo_iter = malloc(sizeof(hash_iter_t));
	if (!nuevo_iter) return NULL;
	
	nuevo_iter->hash = hash;
	nuevo_iter->index = 0;
	while (nuevo_iter->index < hash->tam - 1)
	{
		if (nuevo_iter->hash->vector[nuevo_iter->index]->estado == OCUPADO) break;
		nuevo_iter->index++;
	}
	if (nuevo_iter->hash->vector[nuevo_iter->index]->estado != OCUPADO) nuevo_iter->index = 0;
	return nuevo_iter;	
}
	
bool hash_iter_avanzar(hash_iter_t *iter)
{
	if (!iter) return false;
	if (iter->index == -1) return false;
	
	int pos = iter->index;
	pos++;
	while (pos < iter->hash->tam)
	{
		if (iter->hash->vector[pos]->estado == OCUPADO)
		{
			iter->index = pos;
			return true;
		}
		pos++;
	}
	iter->index = -1;
	return false;
}

const char *hash_iter_ver_actual(const hash_iter_t *iter)
{
	if (!iter) return NULL;

	if (iter->index == -1) return NULL;
	if (iter->hash->vector[iter->index]->estado != OCUPADO) return NULL;
	return (iter->hash->vector[iter->index])->clave;
}

bool hash_iter_al_final(const hash_iter_t *iter)
{
	if (!iter) return false;
	
	int index = iter->index;
	if (iter->index == -1) return true;
	if (iter->hash->vector[index]->estado == OCUPADO) return false;
	index++;
	while(index < iter->hash->tam)
	{
		if (iter->hash->vector[index]->estado == OCUPADO) return false;
		index++;
	}
	return true;
}

void hash_iter_destruir(hash_iter_t* iter)
{
	if (!iter) return;
	free(iter);
}
